package org.example.myleet.p433;

import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class Solution {

    private static final HashMap<Character, char[]> TRANSIT_MAP = new HashMap<>(4);

    static {
        TRANSIT_MAP.put('A', new char[]{'C','G','T'});
        TRANSIT_MAP.put('C', new char[]{'A','G','T'});
        TRANSIT_MAP.put('G', new char[]{'A','C','T'});
        TRANSIT_MAP.put('T', new char[]{'A','G','C'});
    }

    public int minMutation(String start, String end, String[] bank) {
        HashSet<String> bankSet = new HashSet<>();
        for (String b : bank) {
            bankSet.add(b);
        }
        bankSet.add(start);
        if (!bankSet.contains(end)) {
            return -1;
        }
        int step = 0;
        Deque<String> deque = new LinkedList<>();
        deque.offer(start);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; ++i) {
                String candidate = deque.poll();
                if (!bankSet.contains(candidate)) {
                    continue;
                }
                if (end.equals(candidate)) {
                    return step;
                }
                StringBuilder sb = new StringBuilder(candidate);
                for (int j = 0; j < sb.length(); ++j) {
                    char c = sb.charAt(j);
                    char[] transits = TRANSIT_MAP.get(c);
                    for (char transit : transits) {
                        sb.setCharAt(j, transit);
                        String mutation = sb.toString();
                        if (bankSet.contains(mutation)) {
                            deque.offer(mutation);
                        }
                    }
                    sb.setCharAt(j, c);
                }
                bankSet.remove(candidate);
            }
            ++step;
        }
        return -1;
    }
}
